#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dinic.h"
#include "plist.h"
#include "edge.h"

static void print_aux(FILE *f,plist_t path, bool first_time, bool last_time, int step_number, unsigned int total_flow, unsigned int min_flow);
static void blocking_step(network n,network network_helper,
                            bool get_aux, int step_number);

static void delete_edge(network nh, unsigned int from, unsigned int to);

void dinic(network n, bool get_flow, bool get_cut, bool get_aux){
    network nh = NULL;
    bool path_exists = true;
    int step_number = 1;
    assert(n != NULL);
    
    /* Si no esta s o t entonces no hay camino*/    
    if (network_find(n , SOURCE) == NULL || network_find(n , SINK) == NULL){
        printf("No existe camino :'(\n");
        exit(EXIT_FAILURE);
    }
    
    /* Mientras existan caminos */
    while (path_exists){
        
        /* Creamos el network auxiliar*/
        nh = network_helper_create(n);
        
        /* Si no existe un camino en el network auxiliar*/         
        if (!network_path_exists(nh)){
            path_exists = false;
            
            /* Si nos habian pedido que imprimamos el corte lo 
             * calculamos*/
            if (get_cut)
                network_cut_calculate(nh);
            network_destroy(nh);
            break;
        }
        
        /* Si existe camino entonces ejecutamos el paso bloqueante*/
        blocking_step(n,nh,get_aux,step_number);
        
        /* El numero de paso sirve para la impresion del NA*/
        step_number++;
        network_destroy(nh);
    }        

    /* Si nos pidieron que imprimamos el flujo lo calculamos */
    if (get_flow)
        network_flow_calculate(n);
    
}
/*! @fn blocking_step(network n,network network_helper, 
                            bool get_aux, int step_number)
 * @brief      Paso bloqueante del algoritmo de dinic.
 * @pre <code> (n != NULL) </code>
 * @pre <code> (network_helper != NULL) </code>
 * @param n            El network donde se aumentará el flujo.
 * @param nh           El network auxiliar que trataremos de bloquear
 *                       sus caminos.
 * @param get_aux      Indica si hay que imprimir los caminos del NA.
 * @param step_number  Indica cuantas veces se ejecutó el paso
 *                       bloqueante. Se utiliza para poder imprimir los
 *                       caminos correctamente.
 */
static void blocking_step(network n,network network_helper, 
                            bool get_aux, int step_number){
    FILE *f = NULL;
    plist_t path = NULL; 
    node x = NULL;
    node y = NULL;
    bool cont = true;
    bool first_time = true;
    bool last_time = false;
    unsigned int source = SOURCE;
    unsigned int min_flow = 0;
    unsigned int total_flow = 0;
    
    assert(n != NULL);
    assert(network_helper != NULL);
    
    if (get_aux)
        f = fopen("aux.txt","a");
   
   /* Este es el paso bloqueante tal como lo vimos en el teorico, 
    * salvo por el agregado de algunas cosas para poder imprimir los
    * caminos bloquetantes del NA correctamente */
    while(cont){
            /* Creo el camino y pongo el s*/
            path = plist_create();
            x = network_find(network_helper, source);
            plist_append(path, x);

            while (node_name(x) != SINK && cont){
                
                /* Si hay un vecino de x lo agregamos al camino */
                if (node_neighbours_fordward(x)){
                    y = node_get_neighbour(x);
                    plist_append(path,y);
                    x = y;
                }
                /* Si ya no hay mas vecinos*/
                else{
                    
                    /* Si el nodo final no es s, entonces borramos la 
                     * arista que forman 2 ultimos nodos*/
                    if (node_name(x) != source){
                        x = plist_remove_last(path);
                        y = plist_get_last(path);

                        delete_edge(network_helper, node_name(y), 
                                                    node_name(x));
                        
                        x = y;
                    }
                    else
                        /* Si no, ya no hay nada por hacer*/
                        cont = false;
                }
            }
                
            /* Si es 1, entonces tenemos un camino de s a t */
            if (node_name(x) == SINK){
                
                /* Incrementamos los flujos del NA y network */
                min_flow = network_helper_increase_flow(path,
                                                        network_helper);
                network_increase_flow(path,n,min_flow);
                
                /* Si nos piden que imprimamos los caminos, lo hacemos*/
                if (get_aux){
                    print_aux(f,path,first_time,last_time,step_number,
                                total_flow,min_flow);
                    first_time = false;
                    total_flow += min_flow;
                }
            }
            free(path);

    }
    
    if (get_aux){
        last_time = true;
        print_aux(f,path,first_time,last_time,step_number,total_flow,
                min_flow);
        fclose(f);
    }

}

/*! @fn delete_edge(network nh, unsigned int from, unsigned int to)
 * @brief      Borra la arista fromto del network auxiliar nh.
 * @pre <code> (nh != NULL) </code>
 * @param nh   El network auxiliar donde se quiere borrar la arista.
 * @param from El origen de la arista a borrar.
 * @param to   El destino de la arista a borrar.
 */
static void delete_edge(network nh, unsigned int from, unsigned int to){
    node from_node = NULL;
    node to_node = NULL;
    
    assert(nh != NULL);
    
    /* Borro to de los vecinos de from*/
    from_node = network_find(nh,from);
    node_delete_neighbour(from_node,to);
    
    /* Borro from de los vecinos de to*/
    to_node = network_find(nh,to);
    node_delete_neighbour(to_node,from);
}

/*! @fn print_aux(FILE *f,plist_t path, bool first_time, bool last_time, 
 *      int step_number, unsigned int total_flow, unsigned int min_flow)
 *  @brief Imprime los caminos bloqueantes en el archivo f.
 *  @pre <code> (f != NULL) </code>
 *  @pre <code> (path != NULL) </code>
 *  @param path El camino bloqueante.
 *  @param first_time Se usa para indicar la primera ejecución.
 *  @param last_time Se usa para indicar a ultima ejecución.
 *  @param step_number El numero del network auxiliar
 *  @param total_flow El flujo total de un network auxiliar
 *  @param min_flow El flujo de un camino bloqueante.
 */
static void print_aux(FILE *f,plist_t path, bool first_time, bool last_time, 
        int step_number, unsigned int total_flow, unsigned int min_flow){
    node nd = NULL;
    node nd_to = NULL;
    edge e = NULL;
    unsigned int nd_name = 0;
    
    assert(path != NULL);
    assert(f != NULL);
    
    /* Si es la ultima vez que se ejecuta en el paso bloqueante*/
    if (last_time){
        fprintf(f,"El N.A. %d aumenta el flujo en %u.\n\n",step_number, total_flow);
        return;
    }
    
    /* Si es la primera vez que se ejecuta en el paso bloqueante*/
    if (first_time)
        fprintf(f,"N.A. %d:\n",step_number);
    
    /* Recorro e imprimo el camino*/    
    plist_rewind(path);
    nd = plist_get_next(path);
    
    while (nd != NULL){
            nd_name = node_name(nd);
            nd_to = plist_get_next(path);
            
            /* Si se termino el camino terminamos*/
            if (nd_to == NULL){
                fprintf(f,"%u ",nd_name);
                break;
            }
            
            /* Busco la arista de los 2 nodos acutales del camino */
            e = edge_find_node_forw(nd,nd_to);
            
            /* Vemos si está fordward*/
            if (e != NULL)
                fprintf(f,"%u ",nd_name);
                
            /* Si no está, agregamos la flecha */
            else 
                fprintf(f,"%u <- ",nd_name);
            
            /* Avanzamos en el camino */
            nd = nd_to;
    }
    
    fprintf(f,"(flujo transportado: %u)\n", min_flow);
}


